//解法一：动态规划
class Solution {
public:
    int jump(vector<int>& nums) {
        int n=nums.size();
        vector<int> dp(n,0x3f3f3f3f);
        dp[0]=0;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<=i-1;j++)
            {
                if(j+nums[j]>=i)
                {
                    dp[i]=min(dp[j]+1,dp[i]);
                }
            }
        }
        return dp[n-1];
    }
};

//方法2：贪心 每次都是在起跳点起跳考虑可以跳到最远的位置，主要当我们最远位置大于等于我们的最后一个元素的下标 此时的就是最佳答案
//另外每次选择起跳的左端点的时候我们一定是上次right的值+1,因为想要次数少我们要尽可能从大的数开始起跳
class Solution {
public:
    int jump(vector<int>& nums) {
        int n=nums.size();
        int left=0,right=0,ret=0;
        while(right<n-1)
        {
            int tem=0;
            for(int i=left;i<=right;i++)
            {
                cout<<"tem:"<<tem<<endl;
                cout<<"i+nums[i]"<<i+nums[i]<<endl;
               tem=max(tem,i+nums[i]);
               cout<<"tem:"<<tem<<endl;
                cout<<"i+nums[i]"<<i+nums[i]<<endl;
            }
             left=right+1;
              right=tem;
            ret++;
           
                 
        }
        return ret;
    }
};